class Node(object):
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight


class Solution(object):
    def construct(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: Node
        """
        m = len(grid)
        n = m

        def search(x0, y0, x1, y1):
            if x1 - x0 == 1:
                node = Node(grid[x0][y0], 1, None, None, None, None)
            else:
                tl = search(x0, y0, (x1 + x0) // 2, (y1 + y0) // 2)
                bl = search((x1 + x0) // 2, y0, x1, (y1 + y0) // 2)
                tr = search(x0, (y1 + y0) // 2, (x1 + x0) // 2, y1)
                br = search((x1 + x0) // 2, (y1 + y0) // 2, x1, y1)
                if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and tl.val == tr.val == bl.val == br.val:
                    node = Node(grid[x0][y0], 1, None, None, None, None)
                else:
                    node = Node(0, 0, tl, tr, bl, br)
            return node

        return search(0, 0, m, n)

data = Solution()
grid = [[0,1],[1,0]]
print(data.construct(grid))